minimally unsatisfiable formula
Finding the Hardest Formulas for Resolution
Peitl, Tomáš (Friedrich-Schiller-Universität Jena) | Szeider, Stefan (TU Wien)
A CNF formula is harder than another CNF formula with the same number of clauses if it requires a longer resolution proof. In this paper, we introduce resolution hardness numbers; they give for m 1, 2,... the length of a shortest proof of a hardest formula on m clauses. We compute the first ten resolution hardness numbers, along with the corresponding hardest formulas. To achieve this, we devise a candidate filtering and symmetry breaking search scheme for limiting the number of potential candidates for hardest formulas, and an efficient SAT encoding for computing a shortest resolution proof of a given candidate formula.
doi: 10.1613/jair.1.12589
12589
Country:
- North America > United States > Washington > King County > Seattle (0.04)
- North America > United States > Louisiana > Orleans Parish > New Orleans (0.04)
- North America > United States > California > Santa Clara County > San Jose (0.04)
- (8 more...)
Technology: